# coding=utf-8
from collections import deque

from python.unit6_tree.part1_basic.Tree import Tree

#  搜索特定值
class SearchBST:
    # 递归实现
    def searchBST(self, root, val):
        if root is None:
            return None
        if val == root.val:
            return root
        return self.searchBST(root.left if val < root.val else root.right, val)

    def searchBST_2(self, root, val):
        while root:
            if val == root.val:
                return root
            root = root.left if val < root.val else root.right
        return None


if __name__ == "__main__":
    tree = Tree()

    root = tree.init_tree_for_bst_search()
    searchBST = SearchBST()
    res = searchBST.searchBST_2(root, 2)
